typedef int QDataType;
typedef struct QListNode
{
	QDataType data;
	struct QListNode* next;
}QNode;
//声明队列
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

void QueueInit(Queue* q);	//队列初始化
void QueuePush(Queue* q, QDataType x);	//队尾入队列
void QueuePop(Queue* q);	//队头出队列
QDataType QueueFront(Queue* q);	//获取队列头部元素
QDataType QueueBack(Queue* q);	//获取队列尾部元素
bool QueueEmpty(Queue* q);	//判空
int QueueSize(Queue* q);	//获取队列中有效元素个数
void QueueDestroy(Queue* q);	//销毁队列

void QueueInit(Queue* q)
{	
	assert(q);
	q->phead = NULL;
	q->ptail = NULL;
	q->size = 0;
}

void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;
	if (q->ptail == NULL)
	{
		q->phead = q->ptail = newcode;
	}
	else
	{
		q->ptail->next = newcode;
		q->ptail = newcode;
	}
	q->size++;
}

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->phead == NULL;
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->phead == q->ptail)
	{
		free(q->phead);
		q->phead = q->ptail = NULL;
	}
	else
	{
		QNode* next = q->phead->next;
		free(q->phead);
		q->phead = next;
	}
	q->size--;
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->phead->data;
}

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->ptail->data;
}

int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}

void QueueDestroy(Queue* q)
{
	assert(q);
	while (q->phead)
	{
		QNode* next = q->phead->next;
		free(q->phead);
		q->phead = next;
	}
	q->phead = q->ptail = NULL;
	q->size = 0;
}

typedef struct 
{
    Queue q1;
    Queue q2;    
} MyStack;


MyStack* myStackCreate()
{
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(obj->q1));
    QueueInit(&(obj->q2)); 
    return obj;   
}

void myStackPush(MyStack* obj, int x)
{
    //入数据入不为空的队列
    if(!QueueEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q1), x);
    }
    else
    {
        QueuePush(&(obj->q2), x);
    }
}

int myStackPop(MyStack* obj)
{
    //假设法
    Queue* Empty = &(obj->q1);
    Queue* NoneEmpty = &(obj->q2);
    if(!QueueEmpty(&(obj->q1)))
    {
        NoneEmpty = &(obj->q1);
        Empty = &(obj->q2);
    }
    //出数据不为空的倒一下
    while(QueueSize(NoneEmpty) > 1)
    {
        QueuePush(Empty, QueueFront(NoneEmpty));
        QueuePop(NoneEmpty);
    }
    //出不为空的最后一个数据
    int data = QueueBack(NoneEmpty);
    QueuePop(NoneEmpty);
    return data;
}

int myStackTop(MyStack* obj) 
{
    if(!QueueEmpty(&(obj->q1)))
    {
        return QueueBack(&(obj->q1));
    }
    else
    {
        return QueueBack(&(obj->q2));
    }
}

bool myStackEmpty(MyStack* obj)
{ 
    return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}

void myStackFree(MyStack* obj)
{
    QueueDestroy(&(obj->q1));
    QueueDestroy(&(obj->q2));
    free(obj);
}